#include <iostream>
#include <stack>
using namespace std;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> st;
        TreeNode* curr = root;
        int count = 0;
        while (curr != nullptr || !st.empty()) {
            while (curr != nullptr) {
                st.push(curr);
                curr = curr->left;
            }
            curr = st.top();
            st.pop();
            count++;
            if (count == k) { return curr->val; }
            curr = curr->right;
        }
        return -1;
    }
};
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int result = 0;
        int count = 0;
        inorder(root, k, count, result);
    }
private:
    void inorder(TreeNode* node, int k, int& count, int& result) {
        if (node == nullptr)return;
        inorder(node->left, k, count, result);
        count++;
        if (count == k) { result = node->val; return; }
        inorder(node->right, k, count, result);
    }
};